%ordenada(+L)
ordenada([]).
ordenada([_]).
ordenada([X|[Y|XS]]) :- X =< Y, ordenada([Y|XS]).

append([], L, L).
append([X|XS], YS, [X|ZS]) :- append(XS, YS, ZS).

vacia(L) :- length(L, Long), Long = 0.

menoresOIgualesA(_, [], []).
menoresOIgualesA(E, [X|XS], [X|YS]) :- X =< E, menoresOIgualesA(E, XS, YS).
menoresOIgualesA(E, [X|XS], YS) :- X > E, menoresOIgualesA(E, XS, YS).

mayoresA(_, [], []).
mayoresA(E, [X|XS], [X|YS]) :- X > E, mayoresA(E, XS, YS).
mayoresA(E, [X|XS], YS) :- X =< E, mayoresA(E, XS, YS).

%quicksort(+L, -LOrd)
quicksort([], []).
quicksort([X], [X]).
quicksort([X|XS], YS) :- not(vacia(XS)), mayoresA(X, XS, Mayores), menoresOIgualesA(X, XS, MenoresOIguales), quicksort(MenoresOIguales, MenoresOrd), 
							quicksort(Mayores, MayoresOrd), append(MenoresOrd, [X], MenoresOrdYX), append(MenoresOrdYX, MayoresOrd, YS). 

%insertarOrdenado(+X, +L, -LOrd]).
insertarOrdenado(X, [], [X]).
insertarOrdenado(X, [Y], [X|[Y|[]]]) :- X =< Y.
insertarOrdenado(X, [Y], [Y|[X|[]]]) :- X > Y.
insertarOrdenado(X, [Y|[Z|YS]], [Y|[X|[Z|YS]]]) :- Y =< X, X =< Z.
insertarOrdenado(X, [Y|[Z|YS]], [Y|ZS]) :- not((Y =< X, X =< Z)), insertarOrdenado(X, [Z|YS], ZS).

minimo([X], X).
minimo([X|[Y|XS]], Min) :- minimo([Y|XS], Z), Min is min(Z,X).  

sacar(X, L, LSinX) :- append(Parte1, [X|Parte2], L), append(Parte1, Parte2, LSinX).

%insort(+L, -LOrd)
insort([], []).
insort(L, [Y|YS]) :- minimo(L, Y), sacar(Y, L, LSinY), insort(LSinY, YS).
